//https://leetcode.cn/problems/merge-k-sorted-lists/
class Solution1 {
    struct Less
    {
        bool operator()(ListNode* parent, ListNode* child)
        {
            return parent->val > child->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) //用优先级队列(堆)作答
    {
        priority_queue<ListNode*, vector<ListNode*>, Less> pq1;
        for(auto& l: lists)
        {
            if(l) pq1.push(l);
        }

        ListNode* head = new ListNode();
        ListNode* prev = head;

        while(!pq1.empty())
        {
            prev->next = pq1.top();
            pq1.pop();
            prev = prev->next;
            if(prev->next) pq1.push(prev->next);
        }

        prev = head -> next;
        delete head;
        return prev;
    }
};


//https://leetcode.cn/problems/reverse-nodes-in-k-group/
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        ListNode* prev = new ListNode();
        ListNode* ret = prev;
        ListNode* node = head;
        while(node)
        {
            ListNode* node1 = node;
            for(int j = 0; j < k; j++)//确定是否需要翻转
            {
                if(!node1) 
                {
                    prev->next = node;
                    return ret->next;
                }
                node1 = node1->next;
            }
            ListNode* next = nullptr;
            ListNode* l = node;//记录翻转后子链表最后一个节点
            for(int i = 0; i < k; i++)
            {
                next = node->next;

                node->next = prev->next;
                prev->next = node;

                node = next;
            }
            prev = l;
        }
        return ret->next;
    }
};